package com.zj.leetcode.hard.stack;

import java.util.Stack;

/**
 * @program: algorithm
 * @description: 最长有效括号
 * TODO 动态规划
 * 32 longest-valid-parentheses
 * @author: Zhang Bo
 * @create: 2022-01-14 17:05
 **/
public class LongestValidParentheses {
    public static void main(String[] args) {
        String[] ss = {"()())", "(()", "()(()", "(()))()()()()((()))"};
        Solution solution = new LongestValidParentheses().new Solution();
        for (int i = 0; i < ss.length; i++) {
            System.out.println(solution.longestValidParentheses(ss[2]));
        }

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int longestValidParentheses(String s) {
            Stack<Character> stack = new Stack<>();

            int i = 0;
            int max = 0;
            int last = 0;
            int count = 0;
            while (i < s.length()) {
                if (s.charAt(i) == '(') {
                    stack.push(s.charAt(i));
                    i++;
                } else {
                    if (!stack.empty()) {
                        stack.pop();
                        count = count + 2 + last;
                    }
                    i++;
                    max = Math.max(max, count);

                    if(i >= s.length() - 1){
                        break;
                    }
                    if (stack.empty() && s.charAt(i) == '(') {
                        last = max;
                    } else {
                        last = 0;
                    }
                    count = 0;
                }
            }

            return Math.max(max - stack.size(), max);
        }
    }

//leetcode submit region end(Prohibit modification and deletion)

}
